package com.gs.coursera.algorithms.core.tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class OptimalBST {

	int j = 0;

	double cost(double w[], double p[], int n, double d) {
		double weight[] = new double[15];
		double profit[] = new double[15];
		int i; 
		double sp, m, t1, t2, min = 9999;
		if (n == 1)
			return ((1 + d) * p[0]);
		else {
			for (sp = 0, i = 0; i < n; i++) {
				sp += p[i];
				if (i != 0)
					t1 = cost(w, p, i - 1, d + 1);
				else
					t1 = 0;
				if ((n - i - 1) != 0) {
					for (int k = 0; k < n - i - 1; k++) {
						weight[k] = w[k + i + 1];
						profit[k] = p[k + i + 1];
					}
					t2 = cost(weight, profit, n - i - 1, d + 1);
				} else
					t2 = 0;
				if (t1 + t2 < min) {
					min = t1 + t2;
					if (d == 0)
						j = i;
				}
			}
			return (sp + min);
		}
	}

	public static void main(String args[]) throws IOException {
		double w[] = new double[15];
		double p[] = new double[15];
		OptimalBST o = new OptimalBST();
		int i, n;
		System.out.println("Enter the no. of nodes");
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		for (i = 0; i < n; i++) {
			System.out.println("Enter the weight and probability of node " + i);
			w[i] = Double.parseDouble(br.readLine());
			p[i] = Double.parseDouble(br.readLine());
		}
		System.out.println("Solution is : " + o.cost(w, p, n, 0));
		System.out.println("Root is : " + w[o.j]);
	}

}
